function maxSubArray(nums) {
    // 分治法求解最大子数组和
    return divideAndConquer(nums, 0, nums.length - 1)
}

function divideAndConquer(nums, left, right) {
    // 基本情况：如果只有一个元素，返回该元素
    if (left === right) {
        return nums[left]
    }

    // 计算中间点
    const mid = Math.floor((left + right) / 2)

    // 递归求解左半部分和右半部分的最大子数组和
    const leftMax = divideAndConquer(nums, left, mid)
    const rightMax = divideAndConquer(nums, mid + 1, right)

    // 计算跨越中间点的最大子数组和
    const crossMax = maxCrossingSubArray(nums, left, mid, right)

    // 返回三个部分中最大的值
    return Math.max(leftMax, rightMax, crossMax)
}

function maxCrossingSubArray(nums, left, mid, right) {
    // 计算左半部分的最大子数组和
    let leftSum = -Infinity
    let sum = 0
    for (let i = mid; i >= left; i--) {
        sum += nums[i]
        if (sum > leftSum) {
            leftSum = sum
        }
    }

    // 计算右半部分的最大子数组和
    let rightSum = -Infinity
    sum = 0
    for (let i = mid + 1; i <= right; i++) {
        sum += nums[i]
        if (sum > rightSum) {
            rightSum = sum
        }
    }

    // 返回跨越中间点的最大子数组和
    return leftSum + rightSum
}

// 示例测试
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) // 输出：6
console.log(maxSubArray([1])) // 输出：1
console.log(maxSubArray([5, 4, -1, 7, 8])) // 输出：23